1. Field of the Invention
This invention relates in general to computer aided design (CAD) systems, and more particularly, to a method, apparatus and article of manufacture for performing spatial index compression through spatial subdivision encoding.
2. Description of Related Art
Spatial indices are useful in graphical applications such as computer-assisted drafting (CAD), where data has spatial extents and often the user is working with a subset of data defined by a spatial subset of the database extents. In typical CAD applications, the database is saved in a binary file. Since projects are organized and information exchanged through these files, it is beneficial to store data in a compressed form in such a way that access and decoding of the data is efficient as well.
Numerous structures have been proposed to represent spatial data, including an oct-tree and an R-tree, as described in Hanan Samet, "The Design and Analysis of Spatial Data Structures," Addison-Wesley, 1990, which is incorporated by reference herein.
Although the oct-tree structure has the benefit of simplicity, there are limitations to the oct-tree:
Objects that lie on partitioning planes end up near the root, even if they are of small extents. PA1 The oct-tree does not handle data that degenerates along a dimension. For example, if the data set consists of buildings of all the same height (Z extent), they will all end up being classified at the root. The oct-tree lacks the ability to adapt to such a situation. A quad-tree would be an appropriate structure for this case. PA1 Input data distribution can skew the R-tree and make it degenerate fairly easily. For example, if the first object added to the tree spans the database extents, then adding subsequent objects will force the node containing the first (large) object to migrate to a greater depth. So the tree will essentially become linear. This sensitivity to input data distribution makes it necessary to introduce additional heuristics in tree creation in order to control degeneracies.
The R-Tree is object-extent-based, as opposed to global-extent-subdivision-based, as described in A. Guttman, "R-Trees: A Dynamic Index Structure for Spatial Searching," Proceedings of the Annual Meeting ACM SIGMOD, Boston, Mass. 1984, which is incorporated by reference herein.
Although the R-Tree has the advantage of generality, there are also limitations to the R-tree:
The present invention describes a restricted version of the R-tree that enhances the oct-tree to solve specific limitations of the oct-tree. The present invention solves some oct-tree limitations without permitting the degeneracies possible in the general R-tree. For convenience of notation, this structure is called a Cell tree, where each node in the tree is known as a Cell. A pointer-less representation is used for making the structure persistent.